#include<stdio.h>
#include<stdlib.h>

//树节点结构体
typedef struct BiTNode {
    char c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;
typedef BiTree ElemType;
//辅助队列结构体
typedef struct Squeue {
    BiTree addr;
    struct Squeue *next;
} Squeue, *pSqueue;

//队列链表结构体
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

//中序输出(递归)
void InfixOrder(BiTree T) {
    if (T != NULL) {
        InfixOrder(T->lchild);
        putchar(T->c);
        InfixOrder(T->rchild);
    }
}

//后序输出
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        putchar(T->c);
    }
}

//初始化队列(链表)
void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

bool IsEmpty(LinkQueue Q) {
    return Q.rear == Q.front;
}

//入队
void EnQueue(LinkQueue &Q, ElemType element) {
    LinkNode *pnew = (LinkNode *) malloc(sizeof(LinkNode));
    pnew->data = element;
    //当前结点可能为尾结点
    pnew->next = NULL;
    //尾部入队
    Q.rear->next = pnew;
    Q.rear = pnew;//尾指针指向新的尾指针
}

//出队
void DeQueue(LinkQueue &Q, BiTree &element) {
    //判断队列是否为空
    if (IsEmpty(Q)) return;
    LinkNode *q = Q.front->next;
    element = q->data;
    Q.front->next = q->next;//断链
    //假如链表只剩余一个结点时候，被删除后要改变rear
    if (Q.rear == q) {
        Q.rear = Q.front;
    }
    free(q);
}

//层次输出/水平输出
void LevelOrder(BiTree T) {
    LinkQueue Q;
    //初始化队列
    InitQueue(Q);
    BiTree p;//存储出队的结点
    EnQueue(Q, T);//把根入队
    while (!IsEmpty(Q)) {
        DeQueue(Q, p);
        printf("%c", p->c);
        if (p->lchild) {
            EnQueue(Q, p->lchild);
        }
        if (p->rchild) {
            EnQueue(Q, p->rchild);
        }
    }
}


int main() {
    BiTree tree = NULL;
    BiTree pnew;
    char c;
    pSqueue phead = NULL, ptail = NULL, list_pnew = NULL, pcur = NULL;
    //层次建立二叉树
    while (scanf("%c", &c)) {
        if (c == '\n') break;
        //为树节点申请空间
        pnew = (BiTree) calloc(1, sizeof(BiTNode));
        //将申请的结点插入到树中
        pnew->c = c;
        //为队列申请空间
        list_pnew = (pSqueue) calloc(1, sizeof(Squeue));
        list_pnew->addr = pnew;
        if (tree == NULL) {
            tree = pnew;
            phead = list_pnew;
            ptail = list_pnew;
            pcur = list_pnew;
        } else {
            //队尾入队
            ptail->next = list_pnew;
            ptail = list_pnew;
            //若左节点为空
            if (pcur->addr->lchild == NULL) {
                pcur->addr->lchild = pnew;
                //若右节点为空
            } else if (pcur->addr->rchild == NULL) {
                pcur->addr->rchild = pnew;
                pcur = pcur->next;
            }
        }
    }

    //中序输出
    InfixOrder(tree);
    printf("\n");
    //后序输出
    PostOrder(tree);
    printf("\n");
    //层次输出
    LevelOrder(tree);
    return 0;
}
